SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Read–modify–write</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Read–modify–write</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">"RMW" redirects here. For other uses, see <a href="RMW_(disambiguation)" class="mw-disambig" title="RMW (disambiguation)">RMW (disambiguation)</a>.</div>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, <b>read–modify–write</b> is a class of <a href="Atomic_operation" class="mw-redirect" title="Atomic operation">atomic operations</a> (such as <a href="Test-and-set" title="Test-and-set">test-and-set</a>, <a href="Fetch-and-add" title="Fetch-and-add">fetch-and-add</a>, and <a href="Compare-and-swap" title="Compare-and-swap">compare-and-swap</a>) that both read a <a href="Memory_location" class="mw-redirect" title="Memory location">memory location</a> and write a new value into it simultaneously, either with a completely new value or some function of the previous value. These operations prevent <a href="Race_conditions" class="mw-redirect" title="Race conditions">race conditions</a> in multi-threaded applications. Typically they are used to implement <a href="Mutex" class="mw-redirect" title="Mutex">mutexes</a> or <a href="Semaphore_(programming)" title="Semaphore (programming)">semaphores</a>. These atomic operations are also heavily used in <a href="Non-blocking_synchronization" class="mw-redirect" title="Non-blocking synchronization">non-blocking synchronization</a>.

</p><p>Read–modify–write instructions often produce unexpected results when used on <a href="I/O" class="mw-redirect" title="I/O">I/O</a> devices, as a write operation may not affect the same internal <a href="Hardware_register" title="Hardware register">register</a> that would be accessed in a read operation.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> This term is also associated with <a href="RAID" title="RAID">RAID</a> levels that perform actual write operations as <a href="Atomic_operation" class="mw-redirect" title="Atomic operation">atomic</a> read–modify–write sequences.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Such RAID levels include <a href="RAID_4" class="mw-redirect" title="RAID 4">RAID 4</a>, <a href="RAID_5" class="mw-redirect" title="RAID 5">RAID 5</a> and <a href="RAID_6" class="mw-redirect" title="RAID 6">RAID 6</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Consensus_number">Consensus number</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .excerpt-hat .mw-editsection-like{font-style:normal}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable dablink excerpt-hat selfref">This section is an excerpt from <a href="Consensus_(computer_science)#Consensus_number" title="Consensus (computer science)">Consensus (computer science) § Consensus number</a>.<span class="mw-editsection-like "><span class="mw-editsection-bracket">[</span><a class="external text external" href="https://en.wikipedia.org/w/index.php?title=Consensus_(computer_science)&action=edit">edit</a><span class="mw-editsection-bracket">]</span></span></div><div class="excerpt">

<p>To solve the consensus problem in a shared-memory system, concurrent objects must be introduced. A concurrent object, or shared object, is a data structure which helps concurrent processes communicate to reach an agreement. Traditional implementations using <a href="Critical_section" title="Critical section">critical sections</a> face the risk of crashing if some process dies inside the critical section or sleeps for an intolerably long time. Researchers defined <a href="Non-blocking_algorithm#Wait-freedom" title="Non-blocking algorithm">wait-freedom</a> as the guarantee that the algorithm completes in a finite number of steps.

</p><p>The consensus number of a concurrent object is defined to be the maximum number of processes in the system which can reach consensus by the given object in a wait-free implementation.<sup id="cite_ref-Consensus_(computer_science)_hierarchy_3-0" class="reference"><a href="#cite_note-Consensus_(computer_science)_hierarchy-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Objects with a consensus number of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> can implement any object with a consensus number of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> or lower, but cannot implement any objects with a higher consensus number. The consensus numbers form what is called <a href="Maurice_Herlihy" title="Maurice Herlihy">Herlihy</a>'s hierarchy of synchronization objects.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<th>Consensus<br>number</th>

<th>Objects

</th></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math></span><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"></span></td>

<td><a href="Atomic_semantics" title="Atomic semantics">atomic</a> <a href="Shared_register" title="Shared register">read/write registers</a>, <a href="Lock_(computer_science)" title="Lock (computer science)">mutex</a>

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math></span><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy"></span></td>

<td><a href="Test-and-set" title="Test-and-set">test-and-set</a>, <a href="Swap_(computer_programming)" title="Swap (computer programming)">swap</a>, <a href="Fetch-and-add" title="Fetch-and-add">fetch-and-add</a>, wait-free <a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">queue</a> or <a href="Stack_(abstract_data_type)" title="Stack (abstract data type)">stack</a>

</td></tr>

<tr>

<td>...

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2n-2}</annotation>

</semantics>

</math></span><img src="./a8593ff30008d016680ae67c34865b96087b62fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.56ex; height:2.343ex;" alt="{\displaystyle 2n-2}" loading="lazy"></span></td>

<td>n-register assignment

</td></tr>

<tr>

<td>...

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

<td><a href="Compare-and-swap" title="Compare-and-swap">compare-and-swap</a>, <a href="Load-link/store-conditional" title="Load-link/store-conditional">load-link/store-conditional</a>,<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte

</td></tr></tbody></table>

According to the hierarchy, read/write registers cannot solve consensus even in a 2-process system. Data structures like stacks and queues can only solve consensus between two processes. However, some concurrent objects are universal (notated in the table with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \infty }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math></span><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy"></span>), which means they can solve consensus among any number of processes and they can simulate any other objects through an operation sequence.<sup id="cite_ref-Consensus_(computer_science)_hierarchy_3-1" class="reference"><a href="#cite_note-Consensus_(computer_science)_hierarchy-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></div></div>

<ul><li><a href="Linearizability" title="Linearizability">Linearizability</a></li>

<li><a href="Read%E2%80%93erase%E2%80%93modify%E2%80%93write" class="mw-redirect" title="Read–erase–modify–write">Read–erase–modify–write</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://techref.massmind.org/techref/readmodwrite.htm">Massmind: "The read–modify–write problem"</a></span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20210224160746/http://www.ecs.umass.edu/ece/koren/architecture/Raid/basicRAID.html">"Basic RAID Organizations"</a>. <i>umass.edu</i>. Archived from <a rel="nofollow" class="external text" href="http://www.ecs.umass.edu/ece/koren/architecture/Raid/basicRAID.html">the original</a> on 2021-02-24<span class="reference-accessdate">. Retrieved <span class="nowrap">2013-10-04</span></span>.</cite></span>

</li>

<li id="cite_note-Consensus_(computer_science)_hierarchy-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-Consensus_(computer_science)_hierarchy_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Consensus_(computer_science)_hierarchy_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFHerlihy1991" class="citation journal cs1">Herlihy, Maurice (January 1991). <a rel="nofollow" class="external text" href="http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf">"Wait-Free Synchronization"</a> <span class="cs1-format">(PDF)</span>. <i>ACM Transactions on Programming Languages and Systems</i>. <b>11</b> (1): <span class="nowrap">124–</span>149. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F114005.102808">10.1145/114005.102808</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2181446">2181446</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110605003208/http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 5 June 2011<span class="reference-accessdate">. Retrieved <span class="nowrap">19 December</span> 2011</span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFImbsRaynal2010" class="citation book cs1">Imbs, Damien; Raynal, Michel (25 July 2010). <a rel="nofollow" class="external text" href="https://hal.inria.fr/inria-00454399/file/PI-1949.pdf">"The multiplicative power of consensus numbers"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing</i>. Association for Computing Machinery. pp. <span class="nowrap">26–</span>35. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1835698.1835705">10.1145/1835698.1835705</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-60558-888-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3179361">3179361</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220127204746/https://hal.inria.fr/inria-00454399/file/PI-1949.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 27 January 2022<span class="reference-accessdate">. Retrieved <span class="nowrap">22 April</span> 2021</span>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFFichHendlerShavit2004" class="citation book cs1">Fich, Faith; Hendler, Danny; Shavit, Nir (25 July 2004). "On the inherent weakness of conditional synchronization primitives". <i>Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing</i>. Association for Computing Machinery. pp. <span class="nowrap">80–</span>87. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96.9340">10.1.1.96.9340</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1011767.1011780">10.1145/1011767.1011780</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-58113-802-4</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9313205">9313205</a>.</cite></span>

</li>

</ol></div>

<p><br>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-23" href="https://en.wikipedia.org/wiki/?title=Read%E2%80%93modify%E2%80%93write&oldid=1281913553">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>